#include <malloc.h>

#define MAX_EACH_WIDTH 3
#define MIN_EACH_WIDTH 1
#define MAX_EACH_NUM 255
#define IP_NUMS 4

int str_to_num(const char* str_start_p, const char* str_endn_p) {
	int num = 0;
	if (str_start_p + 1 != str_endn_p && *str_start_p == '0') {
		return -1;
	}
	for (const char* p = str_start_p; p < str_endn_p; p++) {
		char ch = *p;
		int bit = ch - '0';
		num = num * 10 + bit;
	}
	if (num > MAX_EACH_NUM) {
		return -1;
	}
	return num;
}

void uint8_to_str_write(char** str_pp, int n) {
	char* p = *str_pp;
	int ori_n = n;
	int h = n / 100;
	n %= 100;
	if (ori_n >= 100) {
		*p = h + '0';
		p++;
	}
	int t = n / 10;
	n %= 10;
	if (ori_n >= 10) {
		*p = t + '0';
		p++;
	}
	*p = n + '0';
	p++;
	*str_pp = p;
}

char* get_valid_ip(const char str_b[], int str_len, char len_b[]) {
	unsigned char ip_num_a[IP_NUMS];
	const char* start_p = str_b;
	const char* endn_p;
	for (int num_index = 0; num_index < IP_NUMS; num_index++) {
		int len = len_b[num_index];
		endn_p = start_p + len;
		int num = str_to_num(start_p, endn_p);
		if (num < 0) {
			return NULL;
		}
		ip_num_a[num_index] = num;
		start_p = endn_p;
	}
	int num_index = 0;
	char* ip_str_b = malloc(sizeof(char[(MAX_EACH_WIDTH + 1) * IP_NUMS]));
	char* ip_str_p = ip_str_b;
	while (1) {
		int ip_num = ip_num_a[num_index];
		uint8_to_str_write(&ip_str_p, ip_num);
		num_index++;
		if (num_index >= IP_NUMS) {
			*ip_str_p = '\0';
			return ip_str_b;
		}
		*ip_str_p = '.';
		ip_str_p++;
	}
}

void append_ip_if_need(char ip_b[], char*** result_bpp) {
	if (ip_b == NULL) {
		return;
	}
	char** result_bp = *result_bpp;
	*result_bp = ip_b;
	result_bp++;
	*result_bpp = result_bp;
}

char** restoreIpAddresses(char str_b[], int* result_num_p) {
	const char* p = str_b;
	while (1) {
		char ch = *p;
		if (ch == '\0') {
			break;
		}
		p++;
	}
	int str_len = p - str_b;

	char** result_bb = malloc(sizeof(char* [27]));
	char** result_bp = result_bb;
	for (int len1 = 1;
	     len1 <= MAX_EACH_WIDTH && len1 + MIN_EACH_WIDTH * 3 <= str_len;
	     len1++) {
		if (len1 + MAX_EACH_WIDTH * 3 < str_len) {
			continue;
		}
		for (int len2 = 1; len2 <= MAX_EACH_WIDTH &&
				   len1 + len2 + MIN_EACH_WIDTH * 2 <= str_len;
		     len2++) {
			if (len1 + len2 + MAX_EACH_WIDTH * 2 < str_len) {
				continue;
			}
			for (int len3 = 1;
			     len3 <= MAX_EACH_WIDTH &&
			     len1 + len2 + len3 + MIN_EACH_WIDTH <= str_len;
			     len3++) {
				if (len1 + len2 + len3 + MAX_EACH_WIDTH <
				    str_len) {
					continue;
				}
				int len4 = str_len - (len1 + len2 + len3);
				char len_a[] = {
					len1,
					len2,
					len3,
					len4,
				};
				char* ip_b =
					get_valid_ip(str_b, str_len, len_a);
				append_ip_if_need(ip_b, &result_bp);
			}
		}
	}
	*result_num_p = result_bp - result_bb;
	return result_bb;
}